package Medium;

import Structures.TreeNode;

import java.util.ArrayList;

public class LC0450 {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;

        TreeNode[] tuple = search(root, null, key); // val等于key的结点
        TreeNode matchNode = tuple[0], matchParent = tuple[1];
        if (matchNode == null) return root; // 没有匹配的结点
        TreeNode retVal = deleteNode(matchNode, matchParent);
        if (matchNode == root) return retVal; // 删除根结点时，直接利用重载函数的返回值
        else return root; // 不需要删除根结点时，将根正常返回
    }

    private static TreeNode[] search(TreeNode node, TreeNode parent, int key) {
        if (node == null || node.val == key) {
            TreeNode[] ret = new TreeNode[2];
            ret[0] = node;
            ret[1] = parent;
            return ret;
        }

        if (key < node.val) return search(node.left, node, key);
        else return search(node.right, node, key);
    }

    /**
     * 从二叉搜索树中删除指定结点node，并返回原先以node为根的子树的新的根结点
     *
     * @param node   待删除的结点
     * @param parent node的亲代结点
     */
    private static TreeNode deleteNode(TreeNode node, TreeNode parent) {
        if (parent != null && (node.left == null || node.right == null)) {
            if (parent.left == node) {
                if (node.left != null) // 右子树为空
                    parent.left = node.left;
                else if (node.right != null) parent.left = node.right;
                else parent.left = null;
                return parent.left;
            }
            else { // parent.right == node
                if (node.left != null)
                    parent.right = node.left;
                else if (node.right != null) parent.right = node.right;
                else parent.right = null;
                return parent.right;
            }
        }
        else { // 非根结点的左右指针均不为空，或者需要删除根结点
            TreeNode vDeleteNode;
            TreeNode deleteParent = node;
            if (node.left == null && node.right == null) return null; // 删除整棵树
            if (node.left != null) {
                vDeleteNode = node.left;
                while (vDeleteNode.right != null) {
                    deleteParent = vDeleteNode;
                    vDeleteNode = vDeleteNode.right;
                } // 到达左子树中最大的结点
            }
            else {
                vDeleteNode = node.right;
                while (vDeleteNode.left != null) {
                    deleteParent = vDeleteNode;
                    vDeleteNode = vDeleteNode.left;
                } // 到达右子树中最小的结点
            }
            node.val = vDeleteNode.val;
            deleteNode(vDeleteNode, deleteParent);
            return node;
        }
    }
}
